public class WiggleSubsequence {
    /*
    * 376. 摆动序列
    * 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。
    * 第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
    * 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
    * 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
    * 子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
    * 给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
    *
    * 1 <= nums.length <= 1000
    * 0 <= nums[i] <= 1000
    * */
    public static void main(String[] args){

    }

    // 我的想法：滑动窗口,理解题意错误！
    // 解答错误
    public int mySolution(int[] nums){
        if(nums == null || nums.length == 0)
            return 0;
        if(nums.length == 1)
            return 1;

        int max = 1;
        int left = 0;
        int right = 2;
        int flag = nums[1] - nums[0];
        while (right < nums.length){
            int diff = nums[right] - nums[right-1];
            if(diff * flag < 0){
                int len = right - left + 1;
                max = Math.max(max, len);
            }
            else {
                left = right - 1;
            }
            flag = diff;
            right++;
        }
        return max;
    }

    // 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
    //整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
    // 这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点
    public int solution(int[] nums){
        if(nums == null || nums.length == 0)
            return 0;
        if(nums.length == 1)
            return 1;

        int flag = 0;
        int diff = 0;
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            diff = nums[i] - nums[i-1];
            // 递增坡和递减坡和平坡不处理，相当于删除元素
            if((diff > 0 && flag <= 0) || (diff < 0 && flag >= 0)){
                res++;
                flag = diff;
            }
        }
        return res;
    }
}
